
package Amazon;

import java.util.Arrays;

/**
 * QUESTION
 * =========
 * Write a function that given an input array of integers with 4 
 * entries and a desired target_sum, returns the number of 
 * combinations, of any length, that add up to that target_sum.
 * 
 * BONUS QUESTION
 * =======================
 * How would you extend it to deal with a varying length input array?
 * 
 * @author Yuan Tao
 *
 */
public class Combinations {
	
	/**
	 * The function takes a varying length integer array and
	 * return the unique number of combinations that add up to the target.
	 * @param num is an integer array of any length.
	 * @param target is the target_sum. 
	 * @return the number of unique combinations that add up to the target.
	 */
	public int combinationSum(int num[],int target){
		if(num == null ||num.length == 0){
			return 0;
		}
		Arrays.sort(num);
		return uniqueCombination(num, target, 0 ,false);
	}
	
	/**
	 * The function is a recursive. It computes all possible combination sums.
	 * And counts the unique combinations.
	 * @param num is the input array.
	 * @param target is the target_sum.
	 * @param start is the start position.
	 * @param nonZero is true when the target is 0.
	 * @return the number of unique combinations.
	 */
	private int uniqueCombination(int num[],long target, int start, boolean nonZero){
        
		int count = 0;
		if(target == 0 && nonZero){
			++count;
		}
		for(int i = start; i < num.length;++i){
			if(num[i] > target){
				return count;
			}
            count += uniqueCombination(num, target-num[i], i+1,true);
			while(i < num.length - 1 && num[i] == num[i+1]){
				++i;
			}
		}
		return count;
	}
	
	
	/**
	 * This is a brute force way to compute the combinations of four numbers.
	 * The length could be 1,2,3,4. So the function counts the number of 
	 * different length of combinations.
	 * @param num is the input array of integers with 4 entities.
	 * @param target is the target_sum.
	 * @return the unique number of combinations.
	 */
	public int fourNumSum(int num[], int target){
		if(num.length != 4){
			System.err.print("The length of input should be four!");
			System.exit(0);
		}
		int result = 0;
		//Combination length = 4
		long sum = num[0] + num[1] + num[2] + num[3];
		if(sum == target){
			++result;
		}
		
		Arrays.sort(num);
		//Combination length = 3 || Combination length = 1
		for(int i = 0; i != num.length;++i){
			if(i > 0 && num[i] == num[i-1]){
				continue;
			}
			//length = 1
			if(num[i] == target){
				++result;
			}
			//length = 3
			if(sum - num[i] == target){
				++result;
			}
		}
		
		//Combination length = 2
		int begin = 0;
		int end = 3;
		while(begin < end){
			if((long)num[begin] + num[end]== (long)target ){
				++result;
				while(begin < end && num[begin] == num[++begin]);
				while(begin < end && num[end] == num[--end]);
			}else if((long)num[begin] + num[end] > (long)target){
				--end;
			}else{
				++begin;
			}
		}
				
		return result;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] num = {Integer.MAX_VALUE,1,-1,Integer.MIN_VALUE};
		Combinations test = new Combinations();
		System.out.println(test.combinationSum(num, 0));
		System.out.println(test.fourNumSum(num, 0));
	}

}
